/*
 * @lc app=leetcode.cn id=22 lang=java
 *
 * [22] 括号生成
 */

// @lc code=start
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        backtracking(n,result,0,0,"");
        return result;
    }
    public void backtracking(int n,List<String> result,int left,int right,String str){
        if ( left < right ){
            return;
        }if ( left == right && right == n){
            result.add(str);
            return;
        }if ( left < n){
            backtracking(n,result,left+1,right,str+'(');
        }if ( right < left){
            backtracking(n,result,left,right+1,str+')');
        }
    }
}
// @lc code=end

